package 贪心算法._605_种花问题;

public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) return true;
        int count = 0, len = flowerbed.length;
        if (len == 1) {
            return flowerbed[0] == 0 && n == 1;
        }
        int i = 0;
        while (i < flowerbed.length) {
            if (flowerbed[i] == 0) {
                if ((i + 1) < len) {
                    if (flowerbed[i + 1] == 0) {
                        flowerbed[i] = 1;
                        count++;
                        if (count == n) {
                            for (int value : flowerbed) {
                                System.out.print(value + " ");
                            }
                            return true;
                        }
                        i += 2;
                    } else {
                        i++;
                    }
                } else {
                    if (flowerbed[i - 1] == 0) {
                        count++;
                        flowerbed[i] = 1;
                        for (int value : flowerbed) {
                            System.out.print(value + " ");
                        }
                        return count == n;
                    }
                    i++;
                }
            } else {
                i += 2;
            }
        }
        for (int value : flowerbed) {
            System.out.print(value + " ");
        }
        return false;
    }

    public static void main(String[] args) {
        int[] flowers = {0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0};
        for (int value : flowers) {
            System.out.print(value + " ");
        }
        System.out.println();
        System.out.println(new Solution().canPlaceFlowers(flowers, 17));
    }
}
